{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 算法作业 Exercise01\n",
    " - 姓名: **芮志清**\n",
    " - 学号: **2018Z8020661080**\n",
    " - 日期: **2018年11月24日**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 题目要求\n",
    "## Exercise (1). \n",
    "  已知一个长度为n 的数组和一个正整数k，并且最多只能使用一个用于交换数组元素的附加空间单元，  \n",
    "  试设计算法得到原数组循环右移k 次的结果并分析算法的时间复杂度。  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 实现思想\n",
    "  设置初始位置分别为0,1,2...d-1(d为n,k的最大公约数)   \n",
    "  以初始位置开始，循环右移k位，到末尾继续从开头开始循环。  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 代码实现（Python）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxDiv(a:int,b:int)->int:\n",
    "    \"\"\"求a,b最大公约数\n",
    "    使用辗转相除法\"\"\"\n",
    "    a,b=max(a,b),min(a,b)\n",
    "    while a%b!=0:\n",
    "        a,b=b,a%b\n",
    "    return b\n",
    "\n",
    "def rightMove(A:list,k:int,isPrint=False)->list:\n",
    "    \"\"\"将列表A循环右移k位,只用一个额外变量\n",
    "    参数:\n",
    "        A: 待移位的列表,其数量为n\n",
    "        k: 移动的位数\n",
    "        ifPrint: 是否打印移位的过程\n",
    "    返回:\n",
    "        A: 待移位的原列表\n",
    "    \"\"\"\n",
    "    \n",
    "    #设定是否打印输出结果\n",
    "    if not isPrint:\n",
    "        def pr(*args,**kwargs):\n",
    "            pass\n",
    "    else:\n",
    "        pr=print\n",
    "    \n",
    "    n=len(A) \n",
    "    pr(\"*\"*20)\n",
    "    pr(\"{n}个数，循环右移{k}位\".format(**locals()))\n",
    "    pr(\"原数组A:{A}\".format(**locals()))\n",
    "    \n",
    "    k=k%n # 对k取余处理，使其小于n\n",
    "    for s in range(maxDiv(n,k)): # 循环，次数为n,k的最大公约数\n",
    "    # 初始位置依次为 0,1,2,...,maxDiv(n,k)-1\n",
    "        p=s # 将当前位置设置为初始移动的位置\n",
    "        temp=A[s] # 把初始位置元素的赋值给temp\n",
    "        pr(\"temp=[{s}]\".format(**locals()))\n",
    "        while True:\n",
    "            pk=(p-k)%n # 待移动的元素为向前数k个元素\n",
    "            if pk==s: # 如果移动到初始位置，则结束循环\n",
    "                break\n",
    "            pr(\"[{pk}]->[{p}]\".format(**locals()))\n",
    "            A[p]=A[pk] # 将待移动元素移动到当前位置\n",
    "            p=pk # 设置当前位置，前移k位\n",
    "        A[p]=temp # 最后将temp的值赋值给p位置，p位置是初始位置右移k位的位置\n",
    "        pr(\"[{p}]=temp\".format(**locals()))\n",
    "    pr(\"移动后A:{A}\".format(**locals()))\n",
    "    return A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 时间复杂度分析"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在计算最大公约数部分，算法的时间复杂度为$O(\\lg(\\min(n,k)))$  \n",
    "本算法只需要对每个位置的数据移动1次，在移动环节，算法的时间复杂度为$O(n)$\n",
    "整体的时间复杂度为$O(n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 代码演示\n",
    "### n=12,k=3时  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "********************\n",
      "12个数，循环右移3位\n",
      "原数组A:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]\n",
      "temp=[0]\n",
      "[9]->[0]\n",
      "[6]->[9]\n",
      "[3]->[6]\n",
      "[3]=temp\n",
      "temp=[1]\n",
      "[10]->[1]\n",
      "[7]->[10]\n",
      "[4]->[7]\n",
      "[4]=temp\n",
      "temp=[2]\n",
      "[11]->[2]\n",
      "[8]->[11]\n",
      "[5]->[8]\n",
      "[5]=temp\n",
      "移动后A:[9, 10, 11, 0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
      "\n",
      "时间测试\n",
      "19.2 µs ± 268 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "rightMove(list(range(12)),3,True)\n",
    "\n",
    "print(\"\\n时间测试\")\n",
    "%timeit rightMove(list(range(12)),3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### n=12,k=9时"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "********************\n",
      "12个数，循环右移9位\n",
      "原数组A:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]\n",
      "temp=[0]\n",
      "[3]->[0]\n",
      "[6]->[3]\n",
      "[9]->[6]\n",
      "[9]=temp\n",
      "temp=[1]\n",
      "[4]->[1]\n",
      "[7]->[4]\n",
      "[10]->[7]\n",
      "[10]=temp\n",
      "temp=[2]\n",
      "[5]->[2]\n",
      "[8]->[5]\n",
      "[11]->[8]\n",
      "[11]=temp\n",
      "移动后A:[3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2]\n",
      "\n",
      "时间测试\n",
      "19.6 µs ± 450 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "rightMove(list(range(12)),9,True)\n",
    "\n",
    "print(\"\\n时间测试\")\n",
    "%timeit rightMove(list(range(12)),9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### n=12,k=7时"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "********************\n",
      "12个数，循环右移7位\n",
      "原数组A:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]\n",
      "temp=[0]\n",
      "[5]->[0]\n",
      "[10]->[5]\n",
      "[3]->[10]\n",
      "[8]->[3]\n",
      "[1]->[8]\n",
      "[6]->[1]\n",
      "[11]->[6]\n",
      "[4]->[11]\n",
      "[9]->[4]\n",
      "[2]->[9]\n",
      "[7]->[2]\n",
      "[7]=temp\n",
      "移动后A:[5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3, 4]\n",
      "\n",
      "时间测试\n",
      "18.7 µs ± 497 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "rightMove(list(range(12)),7,True)\n",
    "\n",
    "print(\"\\n时间测试\")\n",
    "%timeit rightMove(list(range(12)),7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### n=100000,k=2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "时间测试\n",
      "112 ms ± 3.75 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "print(\"\\n时间测试\")\n",
    "A=list(range(100000))\n",
    "%timeit rightMove(A,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### n=100000,k=99999"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "时间测试\n",
      "128 ms ± 18.2 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "print(\"\\n时间测试\")\n",
    "A=list(range(100000))\n",
    "%timeit rightMove(A,99999)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
